package org.basis.algorithm.dp;

/**
 * 打家劫舍问题
 *
 * @author Mr_wenpan@163.com 2022/03/17 16:24
 */
public class Shabaab {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 1, 1};
//        int[] nums = new int[]{2, 1, 1, 2};
        int rob = rob(nums);
        System.out.println(rob);
    }

    public static int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int[] cache = new int[nums.length + 2];
        return process(nums, 0, 0, cache);
    }

    /*
     * 暴力递归 + 剪枝
     */
    public static int process(int[] nums, int index, int money, int[] cache) {
        // 先检查缓存(剪枝)
//        if (cache[index] != 0) {
//            return cache[index];
//        }
        // base case
        if (index >= nums.length) {
            System.out.println("index = " + index + ", money = " + money);
            return money;
        }
        // 偷当前位置(则不能偷下一家)
        int res1 = process(nums, index + 2, money + nums[index], cache);
        // 不偷当前位置
        int res2 = process(nums, index + 1, money, cache);

        int max = Math.max(res1, res2);
        // 将index位置决策后的最大值记录在缓存中（剪枝）
        cache[index] = max;

        return max;
    }

    /*
     * 暴力递归 + 剪枝
     */
    public static int process2(int[] nums, int index, int money) {
        // base case
        if (index >= nums.length) {
            System.out.println("index = " + index + ", money = " + money);
            return money;
        }
        // 偷当前位置(则不能偷下一家)
        int res1 = process2(nums, index + 2, money + nums[index]);
        // 不偷当前位置
        int res2 = process2(nums, index + 1, money);

        int max = Math.max(res1, res2);

        return max;
    }
}
